package com.leetcode.weekly.contest.no288th;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-10 10:58
 */
public class A03_K次增加后的最大乘积 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[] nums = {0, 4};
    int k = 5;
    int maximumProduct = solution.maximumProduct(nums, k);
    System.out.println(maximumProduct);
  }

  static
  class Solution {
    public static final int REMAIN = 10_0000_0000 + 7;
    public int maximumProduct(int[] nums, int k) {
      if (nums.length == 1) {
        return nums[0] + k;
      }
      while (k > 0) {
        int minIndex = 0;
        int secondMinIndex = 0;
        for (int i = 1; i < nums.length; ++i) {
          if (nums[i] < nums[minIndex]) {
            minIndex = i;
          }

          if (nums[i] > nums[minIndex] && (nums[i] < nums[secondMinIndex] || nums[secondMinIndex] == nums[minIndex])) {
            secondMinIndex = i;
          }
        }

        if (nums[minIndex] == nums[secondMinIndex]) {
          int value = k / nums.length;
          int remainder = k % nums.length;
          for (int i = 0; i < nums.length; ++i) {
            nums[i] += (value + (i < remainder ? 1 : 0));
          }
          k = 0;
        } else {
          List<Integer> minIndexes = new ArrayList<>();
          for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == nums[minIndex]) {
              minIndexes.add(i);
            }
          }

          int maxValue = k / minIndexes.size();
          int curMaxValue = nums[secondMinIndex] - nums[minIndex];
          if (maxValue >= curMaxValue) {
            for (int index : minIndexes) {
              nums[index] += curMaxValue;
            }
            k -= (minIndexes.size() * curMaxValue);
          } else {
            int remainder = k % minIndexes.size();
            for (int i = 0; i < minIndexes.size(); ++i) {
              nums[minIndexes.get(i)] += (maxValue + (i < remainder ? 1 : 0));
            }
            k = 0;
          }
        }
      }

      long answer = 1;
      for (int num : nums) {
        answer = (answer * num) % REMAIN;
      }
      return (int) answer;
    }
  }

}
